package a29_CommenAlgorithm.Search;

/**
 * @Author quan
 * @Description 二分查找：要求数组必须是有序的
 * 查找某个元素在数组中的索引
 * @Date 2023/2/20 23:54
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {0,9,18,27,36,47,56,78,98};
        int number = 98;
        System.out.println(binarySearch(arr,number));
    }
    //二分查找方法
    public static int binarySearch(int[] arr, int number){
        //1、定义两个变量记录查找的范围
        int min = 0;
        int max = arr.length-1;
        //2、利用循环不断的找要查找的数据
        while (true){
            if(min>max){
                return -1;
            }
            //找到中间位置的索引
            int mid = (min+max)/2;
            //查找元素在中间元素的左边
            if(arr[mid] > number){
                max = mid-1;
            } else if (arr[mid] < number) {//查找元素在中间元素的右边
                min = mid+1;
            }else{//查找元素与中间值相等
                return mid;
            }
        }
    }
}
